List manipulation in Python

[1,3,5] + [ 3,4,1]

[1, 3, 5, 3, 4, 1]

range(10)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

l = [3,1,4]

[i^2 for i in range(11)]

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Binary words of a given length

List of binary words, recursive version

def Bn(n): if n == 0: return [[]] else: return [[0]+u for u in Bn(n-1)] + [[1]+u for u in Bn(n-1)]

Bn(4)

[[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 1, 1], [0, 1, 0,
0], [0, 1, 0, 1], [0, 1, 1, 0], [0, 1, 1, 1], [1, 0, 0, 0], [1, 0,
0, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 1, 0, 0], [1, 1, 0, 1], [1,
1, 1, 0], [1, 1, 1, 1]]

List of binary words, base 2 version

def binary(n): l = [None]*2^n for i in range(2^n): l[i] = Integer(i).digits(2, padto=n) return l

binary(4)

[[0, 0, 0, 0], [1, 0, 0, 0], [0, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1,
0], [1, 0, 1, 0], [0, 1, 1, 0], [1, 1, 1, 0], [0, 0, 0, 1], [1, 0,
0, 1], [0, 1, 0, 1], [1, 1, 0, 1], [0, 0, 1, 1], [1, 0, 1, 1], [0,
1, 1, 1], [1, 1, 1, 1]]

Iterator fo binary words

class binaryIter(object): def __init__(self, n): self._n = n self._2n = 2^n self._i = 0 def __iter__(self): return self def next(self): if self._i == self._2n: raise StopIteration res = Integer(self._i).digits(2, padto=self._n) self._i += 1 return res

it = iter(binaryIter(3))

it.next()

[0, 1, 0]

list(binaryIter(3))

[[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [1, 0, 1],
[0, 1, 1], [1, 1, 1]]

Generator using the yield keyword

def binaryIterYield(n): for i in range(2^n): yield Integer(i).digits(2, padto=n)

it = iter(binaryIterYield(4))

it.next()

[0, 0, 1, 0]

list(binaryIterYield(4))

[[0, 0, 0, 0], [1, 0, 0, 0], [0, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1,
0], [1, 0, 1, 0], [0, 1, 1, 0], [1, 1, 1, 0], [0, 0, 0, 1], [1, 0,
0, 1], [0, 1, 0, 1], [1, 1, 0, 1], [0, 0, 1, 1], [1, 0, 1, 1], [0,
1, 1, 1], [1, 1, 1, 1]]

Iteration using Gray code

class binaryIterGray(object): def __init__(self, n): self._n = n self._g = [0]*n self._t = range(n+1) def __iter__(self): return self def next(self): i = self._t[0] if i == self._n: raise StopIteration self._g[i] = 1-self._g[i] self._t[0] = 0 self._t[i] = self._t[i+1] self._t[i+1] = i+1 def get(self): return self._g

Beware, you need to copy the list

def listGrayBug(n): it = binaryIterGray(n) res = [it.get()] for _ in it: res.append(it.get()) return res

listGrayBug(3)

[[0, 0, 1], [0, 0, 1], [0, 0, 1], [0, 0, 1], [0, 0, 1], [0, 0, 1],
[0, 0, 1], [0, 0, 1]]

The correct version

def listGray(n): it = binaryIterGray(n) res = [list(it.get())] for _ in it: res.append(list(it.get())) return res

listGray(3)

[[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1],
[1, 0, 1], [0, 0, 1]]

Iteration using gray code, instrumented version

class binaryIterGrayInst(object): def __init__(self, n): self._n = n self._g = [0]*n self._t = range(n+1) self._c = 0 def __iter__(self): return self def next(self): i = self._t[0] print self._c.digits(2, padto=self._n)[::-1], self._t[::-1], i, self._g[::-1] if i == self._n: raise StopIteration self._c += 1 self._g[i] = 1-self._g[i] self._t[0] = 0 self._t[i] = self._t[i+1] self._t[i+1] = i+1 def get(self): return self._g

l = list(binaryIterGrayInst(4))

[0, 0, 0, 0] [4, 3, 2, 1, 0] 0 [0, 0, 0, 0]
[0, 0, 0, 1] [4, 3, 2, 1, 1] 1 [0, 0, 0, 1]
[0, 0, 1, 0] [4, 3, 2, 2, 0] 0 [0, 0, 1, 1]
[0, 0, 1, 1] [4, 3, 2, 1, 2] 2 [0, 0, 1, 0]
[0, 1, 0, 0] [4, 3, 3, 1, 0] 0 [0, 1, 1, 0]
[0, 1, 0, 1] [4, 3, 3, 1, 1] 1 [0, 1, 1, 1]
[0, 1, 1, 0] [4, 3, 2, 3, 0] 0 [0, 1, 0, 1]
[0, 1, 1, 1] [4, 3, 2, 1, 3] 3 [0, 1, 0, 0]
[1, 0, 0, 0] [4, 4, 2, 1, 0] 0 [1, 1, 0, 0]
[1, 0, 0, 1] [4, 4, 2, 1, 1] 1 [1, 1, 0, 1]
[1, 0, 1, 0] [4, 4, 2, 2, 0] 0 [1, 1, 1, 1]
[1, 0, 1, 1] [4, 4, 2, 1, 2] 2 [1, 1, 1, 0]
[1, 1, 0, 0] [4, 3, 4, 1, 0] 0 [1, 0, 1, 0]
[1, 1, 0, 1] [4, 3, 4, 1, 1] 1 [1, 0, 1, 1]
[1, 1, 1, 0] [4, 3, 2, 4, 0] 0 [1, 0, 0, 1]
[1, 1, 1, 1] [4, 3, 2, 1, 4] 4 [1, 0, 0, 0]

Binary words of a given length and number of one

Recursive version

def Bnk(n, k): if k == 0: return [[0]*n] if k == n: return [[1]*n] else: return [[0]+u for u in Bnk(n-1, k)] + [[1]+u for u in Bnk(n-1, k-1)]

l = Bnk(5,3) l

[[0, 0, 1, 1, 1], [0, 1, 0, 1, 1], [0, 1, 1, 0, 1], [0, 1, 1, 1, 0],
[1, 0, 0, 1, 1], [1, 0, 1, 0, 1], [1, 0, 1, 1, 0], [1, 1, 0, 0, 1],
[1, 1, 0, 1, 0], [1, 1, 1, 0, 0]]

Unrank

def unrankBnk(n,k,i): if i >= binomial(n,k): raise ValueError if n == 0: return [] if i < binomial(n-1, k): return [0]+unrankBnk(n-1, k, i) else: return [1]+unrankBnk(n-1, k-1, i-binomial(n-1, k))

def unrankBnk(n,k,i): if i >= binomial(n,k): raise ValueError if k == 0: return [0]*n if k == n: return [1]*n if i < binomial(n-1, k): return [0]+unrankBnk(n-1, k, i) else: return [1]+unrankBnk(n-1, k-1, i-binomial(n-1, k))

all(unrankBnk(5,3, i) == l[i] for i in range(len(l)))

True

l[5]

[1, 0, 1, 0, 1]

binomial(100, 50), 2^64

(100891344545564193334812497256, 18446744073709551616)

Next using a backtracking algorithm

def nextBin(l): i = 0 while i < len(l) and l[i] == 1: l[i] = 0 i += 1 if i == len(l): raise ValueError else: l[i] = 1

l = [1,1,0,1,1]

nextBin(l)

[0, 0, 1, 1, 1]

List using first/next

def listBin(n): l = [0]*n res = [list(l)] try: while True: nextBin(l) res.append(list(l)) except ValueError: pass return res

listBin(4)

[[0, 0, 0, 0], [1, 0, 0, 0], [0, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1,
0], [1, 0, 1, 0], [0, 1, 1, 0], [1, 1, 1, 0], [0, 0, 0, 1], [1, 0,
0, 1], [0, 1, 0, 1], [1, 1, 0, 1], [0, 0, 1, 1], [1, 0, 1, 1], [0,
1, 1, 1], [1, 1, 1, 1]]

binomial(4,2)

[ factorial(2*N)/factorial(N)/factorial(N+1) for N in range(20) ]

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
742900, 2674440, 9694845, 35357670, 129644790, 477638700,
1767263190]

Cours M2 - CombGen